﻿/* $Author: alexander@bsrgin.ru $
 * $Id: LabyrinthGenerator.java 16 2011-11-17 21:32:19Z alexander@bsrgin.ru $
 * 
 * Activity лабиринта.
 */
package ru.habrahabr.prettyalarm;

import java.util.ArrayList;

/**
 * Генератор лабиринта для модели лабиринта {@link LabyrinthModel}.
 * @author basargin
 */
public class LabyrinthGenerator
{
	/**
	 * Коэффициент притягивания первой точки к стенкам value >= 0, чем меньше
	 * число, тем сильнее притягивание. <br>
	 * Если число равно 1, то появление точки около стенки произойдёт в одном
	 * шаге, от стенки лабиринта.
	 */
	private static final int MAGNETISM_OF_WALLS = 3;
	/**
	 * Отталкивание первой точки от угла (0 <= value <= 1), чем больше число,
	 * тем сильне отталкивание точки от угла. <br>
	 * Если число равно 1, то точка появится не ближе 1 шага по прилегающим
	 * стенкам.
	 */
	private static final int STANDOFF_FROM_CORNERS = 1;
	/**
	 * Минимальная длина стенки лабиринта, измеряемая в кол-вом "радиусов"
	 * бегунка. 
	 */
	private static final int MIN_STAGE_RUNNER_DISTANCE = 3;
	
	private static final int WALL_TOP = 0;
	private static final int WALL_RIGHT = 1;
	private static final int WALL_BOTTOM = 2;
	private static final int WALL_LEFT = 3;
	private static final int CORNER_TOP_RIGHT = 0;
	private static final int CORNER_BOTTOM_RIGHT = 1;
	private static final int CORNER_BOTTOM_LEFT = 2;
	private static final int CORNER_TOP_LEFT = 3;
	private static final int DIRECTION_DOWN = 0;
	private static final int DIRECTION_LEFT = 1;
	private static final int DIRECTION_UP = 2;
	private static final int DIRECTION_RIGHT = 3;
	
	/** Код стенки от 0 до 3 по часовой стрелке от полудня */
	private int wall;
	/** Код угла от 0 до 3 по часовой стрелке правого верхнего */
	private int corner;
	/** Кол-во точек координатной сетки по оси y */
	private int y_nodes;
	/** Кол-во точек координатной сетки по оси x */
	private int x_nodes;
	/** Первая опорная точка лабиринта {@link sceleton_point2} */
	private LabyrinthModel.Point sceleton_point1;
	/** Вторая опорная точка лабиринта {@link sceleton_point1} */
	private LabyrinthModel.Point sceleton_point2;
	/** Матрица допустимых переходов (сетка координат) */
	private boolean nodes[][];
	/** Маршрут и расположение узловых точек лабиринта */
	private ArrayList<LabyrinthModel.Point> route;
	
	
	/**
	 * Конструктор генератора лабиринта. Расчёт расположения стенок лабиринта
	 * происходит здесь же. 
	 * @param l x координата левого края области
	 * @param t y координата верхнего края области
	 * @param r x координата правого края области
	 * @param b y координата нижнего края области
	 * @param runner_radius радису бегунка (минимальный offset от стенок заданной области)
	 */
	LabyrinthGenerator(int l, int t, int r, int b, int runner_radius)
	{
		// район перемещения бегунка уменьшается на его радиус (сдвигаем стенки)
		int height = b - t - 2*runner_radius;
		int width = r - l - 2*runner_radius;
		// считаем количество точек координатной сетки
		int stage_runner_distance = MIN_STAGE_RUNNER_DISTANCE * runner_radius;
		y_nodes = (int)(height / stage_runner_distance) + 1;
		x_nodes = (int)(width / stage_runner_distance) + 1;
		nodes = new boolean[x_nodes][y_nodes];
		// снова сдвигаем стенки района перемещения бегунка по расчитанной
		// координатной сетке
		// запоминаем расположение района перемещения бегунка
		int height_half_rest = (height - stage_runner_distance * (y_nodes-1)) / 2;
		int width_half_rest = (width - stage_runner_distance * (x_nodes-1)) / 2;
		// генерируем лабиринт
		route = new ArrayList<LabyrinthModel.Point>();
		generateRoute();
		/*тест:
		for (int y = 0; y < y_nodes; ++y)
		{
			for (int x = 0; x < x_nodes; ++x)
				route.add(new LabyrinthModel.Point(((y%2)==0)?x:(x_nodes-1-x), y));
			if (y != (y_nodes-1)) route.add(new LabyrinthModel.Point(((y%2)==0)?(x_nodes-1):0, y+1));
		}*/
		// пересчитываем текущую сетку координат в реальные координаты
		for (LabyrinthModel.Point point : route)
		{
			point.x = l + width_half_rest + runner_radius + point.x * stage_runner_distance;
			point.y = t + height_half_rest + runner_radius + point.y * stage_runner_distance;
		}
	}
	
	/**
	 * Возвращает список узловых точек лабиринта.
	 * @return список точек
	 */
	public final ArrayList<LabyrinthModel.Point> getRoute()
	{
		return route;
	}
	
	/**
	 * Генерирует маршрут лабиринта (расположение его стенок).
	 */
	private void generateRoute()
	{
		// генерируем первую точку
		LabyrinthModel.Point first = generateFirstPoint();
		route.add(first);
		
		// генерируем опорные точки
		generateSceletonPoints();
		//Log.d("wc", String.valueOf(wall)+":"+String.valueOf(corner));
		//Log.d("first", String.valueOf(first.x).concat(":").concat(String.valueOf(first.y)));
		//Log.d("sceleton1", String.valueOf(sceleton_point1.x).concat(":").concat(String.valueOf(sceleton_point1.y)));
		//Log.d("sceleton2", String.valueOf(sceleton_point2.x).concat(":").concat(String.valueOf(sceleton_point2.y)));

		// заполняем матрицу "занятости" клеток
		nodes[first.x][first.y] = true;
		while (true)
		{
			while (route.size() > 1)
			{
				markNodes(route.get(route.size()-2), route.get(route.size()-1), false);
				route.remove(route.size()-1);
			}
			// генерируем набор последовательных точек от first до sceleton1
			randomize_route = new ArrayList<LabyrinthModel.Point>();
			randomize_route_finish = sceleton_point1;
			if (generateRandomRoute(-1, 4, first) == false) continue;
			for (int i = randomize_route.size()-1; i >= 0; --i)
			{
				//Log.d("res", String.valueOf(randomize_route.get(i).x).concat(":").concat(String.valueOf(randomize_route.get(i).y)) );
				route.add(randomize_route.get(i));
			}
			// генерируем набор последовательных точек от sceleton1 до sceleton2
			randomize_route.clear();
			randomize_route_finish = sceleton_point2;
			if (generateRandomRoute(randomize_route_direction, 4, sceleton_point1) == false) continue;
			for (int i = randomize_route.size()-1; i >= 0; --i)
			{
				//Log.d("res", String.valueOf(randomize_route.get(i).x).concat(":").concat(String.valueOf(randomize_route.get(i).y)) );
				route.add(randomize_route.get(i));
			}
			randomize_route = null;
			break;
		}
	}
	
	/**
	 * Генерирует расположение первой точки лабиринта.
	 * @return первая точка лабиринта (координаты)
	 */
	private LabyrinthModel.Point generateFirstPoint()
	{
		// учитываем магнетизм стенки и отталкивание углов - выбираем
		// местоположение точки
		// расчитываем максимальную отталкивающую силу стенок
		// ~~~~ ~~~~~
		// ~**~ ~~~~~
		// ~**~ ~~*~~
		// ~~~~ ~~~~~
		//      ~~~~~
		int max_center_offset = Math.min((int)((x_nodes-1)/2), (int)((y_nodes-1)/2));
		int wall_offset = Math.min(max_center_offset, MAGNETISM_OF_WALLS);
		wall_offset = (int)(wall_offset * Math.random());
		// расчитываем максимальную отталкивающую силу углов
		// *~~* **~**
		// ~  ~ **~**
		// ~  ~ ~~ ~~
		// *~~* **~**
		//      **~**
		int corner_standoff = Math.min(max_center_offset, STANDOFF_FROM_CORNERS);
		// получаем координаты зоны внутри которой необходимо сгенерировать первую точку
		// magnetism=3, standoff=1:
		//  ~~~ 
		// ~   ~
		// ~   ~
		//  ~~~
		// magnetism=2, standoff=2:
		//   ~~~~  
		//   ~~~~  
		// ~~    ~~
		// ~~    ~~
		// ~~    ~~
		// ~~    ~~
		//   ~~~~  
		//   ~~~~  
		int first_x_nodes = x_nodes - 2*corner_standoff;
		int first_y_nodes = y_nodes - 2*corner_standoff;
		// случайным образом выбираем стенку (код от 0 до 3 по часовой стрелке от полудня)
		wall = (int)(Math.random() * 4);
		// получаем координаты первой точки, по сути используется периметр с удалением wall_offset
		int x, y;// = (int)(Math.random() * 2 * (first_x_nodes + first_y_nodes) + 0.5);
		// "притягиваем" первую точку к стенке
		// расчитываем кода угла (код от 0 до 3 по часовой стрелке правого верхнего)
		switch (wall)
		{
		case WALL_TOP: // верхняя стенка
			x = corner_standoff + (int)(Math.random() * first_x_nodes);
			y = wall_offset;
			corner = (x >= (int)(x_nodes/2)) ? CORNER_TOP_RIGHT : CORNER_TOP_LEFT;
			break;
		case WALL_RIGHT: // правая стенка
			x = x_nodes - wall_offset - 1;
			y = corner_standoff + (int)(Math.random() * first_y_nodes);
			corner = (y >= (int)(y_nodes/2)) ? CORNER_BOTTOM_RIGHT : CORNER_TOP_RIGHT;
			break;
		case WALL_BOTTOM: // нижняя стенка
			x = corner_standoff + (int)(Math.random() * first_x_nodes);
			y = y_nodes - wall_offset - 1;
			corner = (x >= (int)(x_nodes/2)) ? CORNER_BOTTOM_RIGHT : CORNER_BOTTOM_LEFT;
			break;
		case WALL_LEFT:
		default: // левая стенка
			x = wall_offset;
			y = corner_standoff + (int)(Math.random() * first_y_nodes);
			corner = (y >= (int)(y_nodes/2)) ? CORNER_BOTTOM_LEFT : CORNER_TOP_LEFT;
			break;
		}
		// генериуем первую точку
		return new LabyrinthModel.Point(x, y);
	}
	
	/**
	 * Генерирует пару "опорных" точек, автоматически выбирая их расположение
	 * на основе сведений о расположении первой точки. Метод фактически
	 * осуществляет планирование расположения лабиринта "в пространстве" таким
	 * образом, чтобы он занимал максимум пространства, а не "скучивался" в 
	 * каком-то одном углу. <br>
	 * Метод использует поля wall и corner, заполняет поля sceleton_point1 и
	 * sceleton_point2.
	 */
	void generateSceletonPoints()
	{
		sceleton_point1 = new LabyrinthModel.Point(0, 0);
		sceleton_point2 = new LabyrinthModel.Point(0, 0);
		switch (wall)
		{
		case WALL_TOP:
			if (corner == CORNER_TOP_RIGHT) // верхняя стенка, правый угол : (поверху) справа налево, потом вниз направо
			{	// 1~~0~
				// 1~~~~
				// 1~~~~
				// 1~~22
				getFullWallPoint(WALL_LEFT, new ObjectWrapper<LabyrinthModel.Point>(sceleton_point1));
				getFullHalfWallPoint(WALL_BOTTOM, true, new ObjectWrapper<LabyrinthModel.Point>(sceleton_point2));
			}
			else // if (corner == CORNER_TOP_LEFT) // верхняя стенка, левый угол : (слева) вниз, потом направо
			{	// ~0~~2
				// ~~~~2
				// ~~~~2
				// 11~~2
				getFullHalfWallPoint(WALL_BOTTOM, false, new ObjectWrapper<LabyrinthModel.Point>(sceleton_point1));
				getFullWallPoint(WALL_RIGHT, new ObjectWrapper<LabyrinthModel.Point>(sceleton_point2));
			}
			break;
		case WALL_RIGHT:
			if (corner == CORNER_TOP_RIGHT) // правая стенка, верхний угол : (поверху) справа налево, потом вниз
			{	// 1~~~~
				// 1~~~0
				// ~~~~~
				// 22222
				getFullHalfWallPoint(WALL_LEFT, false, new ObjectWrapper<LabyrinthModel.Point>(sceleton_point1));
				getFullWallPoint(WALL_BOTTOM, new ObjectWrapper<LabyrinthModel.Point>(sceleton_point2));
			}
			else // if (corner == CORNER_BOTTOM_RIGHT) // правая стенка, нижний угол : (слева) вниз, потом направо
			{	// ~~~11
				// ~~~~~
				// 2~~~0
				// 2~~~~
				getFullHalfWallPoint(WALL_TOP, true, new ObjectWrapper<LabyrinthModel.Point>(sceleton_point1));
				getFullHalfWallPoint(WALL_LEFT, true, new ObjectWrapper<LabyrinthModel.Point>(sceleton_point2));
			}
			break;
		case WALL_BOTTOM:
			if (corner == CORNER_BOTTOM_RIGHT) // нижняя стенка, правый угол : (понизу) справа налево, потом направо вверх
			{	// ~~~22
				// ~~~~~
				// 1~~~~
				// 1~~0~
				getFullHalfWallPoint(WALL_LEFT, true, new ObjectWrapper<LabyrinthModel.Point>(sceleton_point1));
				getFullHalfWallPoint(WALL_TOP, true, new ObjectWrapper<LabyrinthModel.Point>(sceleton_point2));
			}
			else // if (corner == CORNER_BOTTOM_LEFT) // нижняя стенка, левый угол : (слева) вверх, потом направо вниз
			{	// 11111
				// ~~~~~
				// ~~~~2
				// ~0~~2
				getFullWallPoint(WALL_TOP, new ObjectWrapper<LabyrinthModel.Point>(sceleton_point1));
				getFullHalfWallPoint(WALL_RIGHT, true, new ObjectWrapper<LabyrinthModel.Point>(sceleton_point2));
			}
			break;
		case WALL_LEFT:
		default:
			if (corner == CORNER_BOTTOM_LEFT) // левая стенка, нижний угол : (поверху) справа налево, потом вниз
			{	// 11111
				// ~~~~~
				// 0~~~2
				// ~~~~2
				getFullWallPoint(WALL_TOP, new ObjectWrapper<LabyrinthModel.Point>(sceleton_point1));
				getFullHalfWallPoint(WALL_RIGHT, true, new ObjectWrapper<LabyrinthModel.Point>(sceleton_point2));
			}
			else // if (corner == CORNER_TOP_LEFT) // левая стенка, верхний угол : (слева) вниз, потом направо
			{	// ~~~~2
				// 0~~~2
				// ~~~~~
				// 11111
				getFullWallPoint(WALL_BOTTOM, new ObjectWrapper<LabyrinthModel.Point>(sceleton_point1));
				getFullHalfWallPoint(WALL_RIGHT, false, new ObjectWrapper<LabyrinthModel.Point>(sceleton_point2));
			}
			break;
		}
	}
	
	/**
	 * Генерирует координаты точки, расположенной на указанной стене.
	 * Изменяет переменную sceleton_x и sceleton_y.
	 * @param wall код стенки от 0 до 3 по часовой стрелке от полудня
	 * @param sceleton_point координаты опорной точки
	 */
	void getFullWallPoint(int wall, ObjectWrapper<LabyrinthModel.Point> sceleton_point)
	{
		double f = Math.random();
		switch (wall)
		{
		case WALL_TOP: // верхняя стенка
			sceleton_point.value.x = (int)(f * x_nodes - 0.5);
			sceleton_point.value.y = 0;
			break;
		case WALL_RIGHT: // правая стенка
			sceleton_point.value.x = x_nodes - 1;
			sceleton_point.value.y = (int)(f * y_nodes - 0.5);
			break;
		case WALL_BOTTOM: // нижняя стенка
			sceleton_point.value.x = (int)(f * x_nodes - 0.5);
			sceleton_point.value.y = y_nodes - 1;
			break;
		case WALL_LEFT:
		default: // левая стенка
			sceleton_point.value.x = 0;
			sceleton_point.value.y = (int)(f * y_nodes - 0.5);
		}
	}
	
	/**
	 * Генерирует координаты точки, насположенной на половине указанной стены.
	 * Изменяет переменную sceleton_x и sceleton_y.
	 * @param wall код стенки от 0 до 3 по часовой стрелке от полудня
	 * @param tail признак "конца" стены (признак использования старших координат) 
	 * @param sceleton_point координаты опорной точки
	 */
	void getFullHalfWallPoint(int wall, boolean tail, ObjectWrapper<LabyrinthModel.Point> sceleton_point)
	{
		double f = Math.random();
		int half_x_nodes = (int)(f * (x_nodes / 2));
		int half_y_nodes = (int)(f * (y_nodes / 2));
		switch (wall)
		{
		case WALL_TOP: // верхняя стенка
			sceleton_point.value.x = tail ? (x_nodes - 1 - half_x_nodes) : half_x_nodes;
			sceleton_point.value.y = 0;
			break;
		case WALL_RIGHT: // правая стенка
			sceleton_point.value.x = x_nodes - 1;
			sceleton_point.value.y = tail ? (y_nodes - 1 - half_y_nodes) : half_y_nodes;
			break;
		case WALL_BOTTOM: // нижняя стенка
			sceleton_point.value.x = tail ? (x_nodes - 1 - half_x_nodes) : half_x_nodes;
			sceleton_point.value.y = y_nodes - 1;
			break;
		case WALL_LEFT:
		default: // левая стенка
			sceleton_point.value.x = 0;
			sceleton_point.value.y = tail ? (y_nodes - 1 - half_y_nodes) : half_y_nodes;
		}
	}
	
	/** Направление последнего сегмента лабиринта, после успешного вызова {@link generateRandomRoute} */
	private int randomize_route_direction;
	/** Конечная точка лабиринта, которую должен достичь метод {@link generateRandomRoute} */
	private LabyrinthModel.Point randomize_route_finish;
	/** Список точек маршрута, после успешного вызова {@link generateRandomRoute} */
	private ArrayList<LabyrinthModel.Point> randomize_route;
	
	/**
	 * Рекурсивный генератор пути с учётом опорной точки, заданной с помощью
	 * поля {@link randomize_route}. В случае успешного прокладывания пути,
	 * генератор устанавливает поле {@link randomize_route_direction} с тем,
	 * чтобы следующая попытка удлиннения пути производилась с учётом направления
	 * последнего сегмента лабиринта. Генератор должен достичь точку заданную
	 * полем {@link randomize_route_finish}.
	 * @param direction код направления: 0-вниз, 1-влево, 2-вверх, 3-направо
	 * @param step_left ограничение рекурсивного подъёма (кол-во оставшихся сегментов)
	 * @param current текущая точка лабиринта
	 * @return признак успешного окончания работы метода
	 */
	private boolean generateRandomRoute(int direction, int step_left, final LabyrinthModel.Point current)
	{
		if (step_left < 0) return false;
		if (current.x == randomize_route_finish.x && current.y == randomize_route_finish.y)
		{
			randomize_route_direction = direction;
			return true;
		}
		int current_direction = generateRandomDirection(direction);
		for (int i = 0; i < 4; i++)
		{
			if (direction == -1)
				current_direction = (current_direction + i) % 4;
			else if (i == 2)
				break;
			else if (i == 1)
				current_direction = (current_direction + 2) % 4;
			//Log.d("try",
			//		String.valueOf(current.x).concat(":").concat(String.valueOf(current.y)).
			//		concat("(").concat(String.valueOf(direction)).concat(")->(").
			//		concat(String.valueOf(current_direction)).concat(")?:?") );
			int x_offset = 0;
			int y_offset = 0;
			int x_left = -1; 
			int y_left = -1; 
			switch (current_direction)
			{
			case DIRECTION_DOWN:
				y_left = y_nodes - 1 - current.y;
				if (y_left == 0) continue;
				y_offset = Math.min(y_left, 1+(int)(y_left*Math.random()));
				break;
			case DIRECTION_LEFT:
				x_left = current.x;
				if (x_left == 0) continue;
				x_offset = -Math.min(x_left, 1+(int)(x_left*Math.random()));
				x_left = -x_left;
				break;
			case DIRECTION_UP:
				y_left = current.y;
				if (y_left == 0) continue;
				y_offset = -Math.min(y_left, 1+(int)(y_left*Math.random()));
				y_left = -y_left;
				break;
			case DIRECTION_RIGHT:
				x_left = x_nodes - 1 - current.x;
				if (x_left == 0) continue;
				x_offset = Math.min(x_left, 1+(int)(x_left*Math.random()));
				break;
			}
			
			// в этой точке известно random-смещение от current-точки в указанном
			// direction-направлении
			// с помощью ограниченного step_left-параметра начинаем рекурсивный
			// подъём в течение которого проверяем достижение randomize_route_finish-точки
			// если точка не найдена, то на рекурсивных спусках пытаемся сначала
			// увеличением x_offset/y_offset, а потом уменьшением повторить
			// операцию прокладывания пути
			// в результате будет найден маршрут из сегментов, количество которых
			// не более step_left-парамера первого вызова метода 
			
			LabyrinthModel.Point next = new LabyrinthModel.Point(current.x+x_offset, current.y+y_offset);
			if (isNodesVacant(current, next))
			{
				//Log.d("next1",
				//		String.valueOf(current.x).concat(":").concat(String.valueOf(current.y)).
				//		concat("(").concat(String.valueOf(direction)).concat(")->(").
				//		concat(String.valueOf(current_direction)).concat(")").
				//		concat(String.valueOf(next.x).concat(":").concat(String.valueOf(next.y))) );
				markNodes(current, next, true);
				if (generateRandomRoute(current_direction, step_left-1, next))
				{
					randomize_route.add(next);
					return true;
				}
				markNodes(current, next, false);
			}
			
			if (x_left > 0)
			{
				int step = (x_left>0) ? +1 : -1;
				for (int j = x_offset+step; j <= x_left; j+=step)
				{
					next = new LabyrinthModel.Point(current.x+j, current.y);
					if (!isNodesVacant(current, next)) continue;
					//Log.d("next2",
					//		String.valueOf(current.x).concat(":").concat(String.valueOf(current.y)).
					//		concat("(").concat(String.valueOf(direction)).concat(")->(").
					//		concat(String.valueOf(current_direction)).concat(")").
					//		concat(String.valueOf(next.x).concat(":").concat(String.valueOf(next.y))) );
					markNodes(current, next, true);
					if (generateRandomRoute(current_direction, step_left-1, next))
					{
						randomize_route.add(next);
						return true;
					}
					markNodes(current, next, false);
				}
				for (int j = x_offset-step; j > 0; j-=step)
				{
					next = new LabyrinthModel.Point(current.x+j, current.y);
					if (!isNodesVacant(current, next)) continue;
					//Log.d("next3",
					//		String.valueOf(current.x).concat(":").concat(String.valueOf(current.y)).
					//		concat("(").concat(String.valueOf(direction)).concat(")->(").
					//		concat(String.valueOf(current_direction)).concat(")").
					//		concat(String.valueOf(next.x).concat(":").concat(String.valueOf(next.y))) );
					markNodes(current, next, true);
					if (generateRandomRoute(current_direction, step_left-1, next))
					{
						randomize_route.add(next);
						return true;
					}
					markNodes(current, next, false);
				}
			}
			if (y_left > 0)
			{
				int step = (y_left>0) ? +1 : -1;
				for (int j = y_offset+step; j <= y_left; j+=step)
				{
					next = new LabyrinthModel.Point(current.x, current.y+j);
					if (!isNodesVacant(current, next)) continue;
					//Log.d("next4",
					//		String.valueOf(current.x).concat(":").concat(String.valueOf(current.y)).
					//		concat("(").concat(String.valueOf(direction)).concat(")->(").
					//		concat(String.valueOf(current_direction)).concat(")").
					//		concat(String.valueOf(next.x).concat(":").concat(String.valueOf(next.y))) );
					markNodes(current, next, true);
					if (generateRandomRoute(current_direction, step_left-1, next))
					{
						randomize_route.add(next);
						return true;
					}
					markNodes(current, next, false);
				}
				for (int j = y_offset-step; j > 0; j-=step)
				{
					next = new LabyrinthModel.Point(current.x, current.y+j);
					if (!isNodesVacant(current, next)) continue;
					//Log.d("next5",
					//		String.valueOf(current.x).concat(":").concat(String.valueOf(current.y)).
					//		concat("(").concat(String.valueOf(direction)).concat(")->(").
					//		concat(String.valueOf(current_direction)).concat(")").
					//		concat(String.valueOf(next.x).concat(":").concat(String.valueOf(next.y))) );
					markNodes(current, next, true);
					if (generateRandomRoute(current_direction, step_left-1, next))
					{
						randomize_route.add(next);
						return true;
					}
					markNodes(current, next, false);
				}
			}
		}
		return false;
	}
	
	/**
	 * Перевод узловых точек лабиринта в доступное/недоступное состояние.
	 * Изменениям подвергаются все точки от from до to.
	 * @param from исходная точка (доступность в этой точке не меняется)
	 * @param to конечная точка
	 * @param flag признак доступности/недоступности точек
	 */
	void markNodes(final LabyrinthModel.Point from, final LabyrinthModel.Point to, boolean flag)
	{
		if (from.x == to.x) // вертикально
		{
			int step = (from.y > to.y) ? -1 : +1, y = from.y;
			do {
				y += step;
				nodes[from.x][y] = flag;
			} while (y != to.y);
		}
		else // горизонтально
		{
			int step = (from.x > to.x) ? -1 : +1, x = from.x;
			do {
				x += step;
				nodes[x][from.y] = flag;
			} while (x != to.x);
		}
	}
	
	/**
	 * Проверка узловых точек лабиринта на предмет их доступности для положения
	 * нового пути.
	 * @param from исходная точка (доступность в этой точке не проверяется)
	 * @param to конечная точка
	 * @return признак доступности всех точек от from до to
	 */
	boolean isNodesVacant(final LabyrinthModel.Point from, final LabyrinthModel.Point to)
	{
		if (from.x == to.x) // вертикально
		{
			int step = (from.y > to.y) ? -1 : +1, y = from.y;
			do {
				y += step;
				if (nodes[from.x][y]) return false;
			} while (y != to.y);
		}
		else // горизонтально
		{
			int step = (from.x > to.x) ? -1 : +1, x = from.x;
			do {
				x += step;
				if (nodes[x][from.y]) return false;
			} while (x != to.x);
		}
		return true;
	}
	
	/**
	 * Генерирует случайное направление маршрута лабиринта. Возвращает код от
	 * 0 до 3, соответственно по часовой стрелке от полудня направление к центру.
	 * Метод учитыват предыдущее направление движения (если
	 * {@link currentDirection} >= 0) и допускает изменение направления +90 и
	 * -90 градусов.
	 * @param currentDirection предыдущее направление 
	 * @return код направления: 0-вниз, 1-влево, 2-вверх, 3-направо 
	 */
	private int generateRandomDirection(int currentDirection)
	{
		if (currentDirection < 0)
			return (int)(4*Math.random());
		else
		{
			switch ((int)(2*Math.random()))
			{
			case 0: currentDirection--; break;
			default: currentDirection++; break; // case 1:
			}
			return (currentDirection + 4) % 4;
		}
	}
	
	/**
	 * Helper-обёртка для модификации объектов типа {@link T}
	 * @param <T>
	 */
	private class ObjectWrapper<T>
	{
		public T value;
		
		/**
		 * Конструктор экземпляра класса без инициализации объекта
		 */
		@SuppressWarnings("unused")
		ObjectWrapper() {
			value = null;
		}
		
		/**
		 * Конструктор экземпляра класса с инициализацией reference на объект
		 * @param value reference на сконструированный объект
		 */
		ObjectWrapper(T value) {
			this.value = value;
		}
	}
}
